package com.love.labuladong.str;

import java.util.Arrays;

/**
 * @Author : zh
 * @Description :
 * @Date : 2024-08-22 17:03
 */
public class KMP {


    // kmp算法
    public static int kmp(char[] s1,char[] s2){
        // s1中当前比对的位置是x
        // s2中当前比对的位置是y
        int n = s1.length;
        int m = s2.length;
        int x = 0;
        int y = 0;

        int[] next = nextArray(s2,m);
        while ( x < n && y < m){
          if(s1[x] == s2[y]){
              x++;
              y++;
          }else if(y == 0){
              x++;
          }else {
              y = next[y];
          }
        }
        return y == m ? x - y : -1;
    }

    // next 数组 ： 前缀和后缀的最大匹配长度
    // 含义: 不包含当前位置字符,前面的字符串的前缀和后缀最大匹配长度，同时字符串不能包含整体


    // m 为s 的长度
    public static int[] nextArray(char[] s, int m) {
        if(m == 1){
            return new int[]{-1};
        }
        int[] next = new int[m];
        next[0] = -1;
        next[1] =  0;
        // i 表示当前要求next值的位置
        // cn : 表示 i 位置前面字符串的最大前后缀长度
        //char[] s = {'a','b','s','a','b','t','k'};
        // next = [-1, 0, 0, 0, 1, 2, 0]
        // 当 i = 2 时， s[i - 1] = 'b',那next[i-1] = 0 = cn,


        // cn 表示 走到i位置，为了快速计算出next[i]，根据 s[i]前一个位置s[i-1]最大前缀后一个字母比较，
        // cn 在一次能找到的情况下，一直向前稳步推进，或者退后再向前推进，s[i]没有最大前后缀，则cn就在0位置呆着
        int i = 2,cn = 0;
        while (i < m){
            // 不用跳
            if(s[i -1] == s[cn]){
                next[i++] = ++cn;
            }else if(cn > 0){
                // cn 出来主要解决这个跳的问题
                cn = next[cn];
            }else {
                next[i++] = 0;
            }
        }
        return next;
    }


    public static void main(String[] args) {
        char[] chs = {'a','b','s','a','b','t','k'};
        // next = [-1, 0, 0, 0, 1, 2, 0]
        // 含义: 不包含当前位置字符,前面的字符串的前缀和后缀最大匹配长度，同时字符串不能包含整体
        // 如上例： 0 位置前面没有字符串，直接 -1
        //         1 位置前面就一个“a”,但是前后缀又不能包含“a”整体本身，相当于就“”，直接0
        //         2 位置就看 “ab”,相当于 0 和 1 位置，此时前缀只有一个“a”,后缀只有一个"b"，显然不相等直接0，如果相等则 1
        //         ...................
        int[] ints = nextArray(chs, chs.length);

        System.out.println(Arrays.toString(ints));


//        String s1 = "tabcsbabcl";
//        String s2 = "abc";
//
//        char[] ch1 = s1.toCharArray();
//        char[] ch2 = s2.toCharArray();
//
//        int kmp = kmp(ch1, ch2);
//
//        System.out.println(kmp);
        String s1 = "aabaaabaaac";
        String s2 = "aabaaac";

    }


}
